package org.aplombh.java.awcing.basic.basics.discretization;

import java.util.*;

/**
 * 假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
 * <p>
 * 现在，我们首先进行 n 次操作，每次操作将某一个位置 x 上的数加 c。
 * <p>
 * 接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。
 * <p>
 * 输入格式
 * 第一行包含两个整数 n 和 m。
 * <p>
 * 接下来 n 行，每行包含两个整数 x 和 c。
 * <p>
 * 再接下来 m 行，每行包含两个整数 l 和 r。
 * <p>
 * 输出格式
 * 共 m 行，每行输出一个询问中所求的区间内数字和。
 * <p>
 * 数据范围
 * −109≤x≤109,
 * 1≤n,m≤105,
 * −109≤l≤r≤109,
 * −10000≤c≤10000
 * 输入样例：
 * 3 3
 * 1 2
 * 3 6
 * 7 5
 * 1 3
 * 4 6
 * 7 8
 * 输出样例：
 * 8
 * 0
 * 5
 */
public class intervalSum_802 {
    // Because alls and array a store three times as much data,define three times the maximum number
    // alls数组需要三倍存储空间，存储请求的l和r下标
    public static final int N = 300010;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] a = new int[N];
        int[] s = new int[N];

        List<Integer> alls = new ArrayList<>();
        Map<Integer, Integer> add = new HashMap<>();
        Map<Integer, Integer> query = new HashMap<>();

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        while (n-- != 0) {
            int x = scanner.nextInt();
            int c = scanner.nextInt();

            // Store insert information
            // 存储插入信息
            add.put(x, c);
            // Store all possible subscripts in alls
            // 存储所有出现的下标
            alls.add(x);
        }
        while (m-- != 0) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();

            // Store query information
            // 存储查询信息
            query.put(l, r);

            // Store all possible subscripts in alls
            // 存储所有出现的下标
            alls.add(l);
            alls.add(r);
        }

        // Sort and distinct the data in alls and stored in all array
        // 将所有下标排序去重
        Integer[] all = alls.stream().sorted().distinct().toArray(Integer[]::new);

        for (Map.Entry<Integer, Integer> item : add.entrySet()) {
            // Gets the index of the position to be added in the array
            // 找到添加数在数组中的下标
            int x = find(item.getKey(), all);
            // Adds data to the specified location in array a
            // 将值添加进数组中
            a[x] += item.getValue();
        }

        // Get prefix sum
        // 获得前缀和
        for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

        for (Map.Entry<Integer, Integer> item : query.entrySet()) {
            // Gets the left index and right index of the position in array all
            // 获取请求下标在数组中的位置
            int l = find(item.getKey(), all), r = find(item.getValue(), all);
            // Get result
            // 获取区间值
            System.out.println(s[r] - s[l - 1]);
        }
    }

    /**
     * 找到值在数组中的下标
     * Find the index of x in array all
     * @param x x
     * @param all array all
     * @return index
     */
    public static int find(int x, Integer[] all) {
        int l = 0, r = all.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (x <= all[mid]) r = mid;
            else l = mid + 1;
        }
        return r + 1;
    }
}
